#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
	struct node *left;
	struct node *right;
	int val;
}bi_tree_t;

static bi_tree_t *inorder_suc(bi_tree_t *root, bi_tree_t *node)
{
	static int found = 0;
	bi_tree_t *n = NULL;
	if (root == NULL) return NULL;
	if ((n = inorder_suc(root->left, node))) return n; 
	if (found == 1) return root;
	if (root->val == node->val) found = 1;
	if ((n = inorder_suc(root->right, node))) return n;
}
static int is_binary_search_tree(bi_tree_t *root)
{
	if(!root) return 1;
	if (!root->left && !root->right) {
		return 1;
	} else if (!root->left && root->right) {
		if (root->val < root->right->val) {
			return 1;
		} else {
			return 0;
		}
	} else if (root->left && !root->right) {
		if (root->val > root->left->val) {
			return 1;
		} else {
			return 0;
		}
	} else if (root->left && root->right) {
		if (root->val > root->left->val && root->val < root->right->val) {
			return 1;
		} else {
			return 0;
		}
	}
	if (is_binary_search_tree(root->left) == 0) {
		return 0;
	}

	if (is_binary_search_tree(root->right) == 0) {
		return 0;
	}
	return 1;
}
#define INT_MIN (-0x7fffffff)
#define INT_MAX (0x7fffffff)
static int is_bst1(bi_tree_t *root, int min, int max)
{
	if (!root) return 1;
	printf("root->val %d: %d, %d\n", root->val, min, max);
	if (root->val > max || root->val < min) return 0;
	
	return is_bst1(root->left, min, root->val - 1) && is_bst1(root->right, root->val + 1, max);
}
static int is_binary_search_tree1(bi_tree_t *root)
{
	return is_bst1(root, INT_MIN, INT_MAX);
}

static int is_binary_search_tree2(bi_tree_t *root)
{
	static bi_tree_t *prev_node = NULL;

	if (!root) return 1;

	if (is_binary_search_tree2(root->left) == 0) 
		return 0;
	if (prev_node && prev_node->val > root->val){
		return 0;
	}
	prev_node = root;
	return is_binary_search_tree2(root->right);
}
static bi_tree_t *find_smallest_node(bi_tree_t *root)
{
	bi_tree_t *n = root;
	while (n) {
		if (n->left) {
			n = n->left;
		} else {
			return n;
		}
	}
	return n;
}
static bi_tree_t *in_order_succeesor(bi_tree_t *root, bi_tree_t *node)
{
	bi_tree_t *suc = NULL;
	if (!root || !node) return NULL;

	if (node->right) {
		suc = node->right;
		while (suc->left) {
			suc = suc->left;
		}
	} else {
		while (root) {
			if (node->val < root->val) {
				suc =  root;
				root = root->left;
			} else if (node->val > root->val) {
				root = root->right;
			} else {
				break;
			}
			
		}
	}
	return suc;
}

static bi_tree_t *find_node(bi_tree_t *root, int val)
{
	if (root == NULL) return NULL;
	while (root) {
		if (root->val == val)
			return root;
		if (val > root->val) {
			root = root->right;
		} else {
			root = root->left;
		}
	}
	return NULL;
}

static int inorder_visit(bi_tree_t *root)
{
	if (root == NULL) return;
	inorder_visit(root->left);
	printf("%d  ", root->val);
	inorder_visit(root->right);
}
static int preorder_visit(bi_tree_t *root)
{
	if (root == NULL) return;
	printf("%d  ", root->val);
	preorder_visit(root->left);
	preorder_visit(root->right);
}

static int postorder_visit(bi_tree_t *root)
{
	if (root == NULL) return;
	postorder_visit(root->left);
	postorder_visit(root->right);
	printf("%d  ", root->val);
}

static int insert_bst(bi_tree_t **root, bi_tree_t *node)
{
	if (!*root) {
		*root = node;
		return 0;
	} else if ((*root)->val == node->val) {
		return -1;
	} else if ((*root)->val > node->val) {
		if (!(*root)->left) {
			(*root)->left = node;
			return 0;
		} else {
			if (insert_bst(&(*root)->left, node) == 0)
				return 0;
		}
	} else {
		if (!(*root)->right) {
			(*root)->right = node;
			return 0;
		} else {
			if (insert_bst(&(*root)->right, node) == 0)
				return 0;
		}
	}
	return -1;
}

bi_tree_t *insert_bst_1(bi_tree_t *root, bi_tree_t *node)
{
	if (root) {
		return node;
	} else if (root->val == node->val) {
		return root;
	} else if (root->val > node->val) {
		if (!root->left) {
			root->left = node;
			return root;
		} else {
			if (insert_bst_1(root->left, node))
				return root;
		}
	} else {
		if (!root->right) {
			root->right = node;
			return root;
		} else {
			if (insert_bst_1(root->right, node))
				return root;
		}
	}
	return root;
}

int del_node(bi_tree_t *root)
{
	bi_tree_t *p = NULL;
	if (!root)  return -1;
	//root is leaf, delete it.
	if (!root->left && !root->right) {
		free(root);
		root = NULL;
		return 0;
	} else if (!root->left) {
		p = root->right;
		root->val = p->val;
		root->left = p->left;
		root->right = p->right;
		free(p);
		root = NULL;
		return 0;
	} else if (!root->right) {
		p = root->left;
		root->val = p->val;
		root->left = p->left;
		root->right = p->right;
		free(p);
		root = NULL;
		return 0;
	} else {
		p = in_order_succeesor(root, root);
		root->val = p->val;
		root->left = p->left;
		root->right = p->right;
		free(p);
		root = NULL;
		return 0;
	}
	return -1;
}

int del_bst_node(bi_tree_t *root, int v)
{
	if (!root) return -1;
	if (root->val == v) {
		return del_node(root);
	}
	if (root->val > v) {
		return del_bst_node(root->left, v);
	} else {
		return del_bst_node(root->right, v);
	}
	return -1;
}
static bi_tree_t *rebuild_pre_in_order(int *pre, int *in, int len)
{
	int i;
	bi_tree_t *root = NULL;
	if (len <= 0) return root;
	for (i = 0; i < len && in[i] != pre[0]; i++);
	root = malloc(sizeof(bi_tree_t));
	root->val = pre[0];
	//root->left = root->right = NULL;
	root ->left = rebuild_pre_in_order(pre+1, in, i);
	root->right = rebuild_pre_in_order(pre+i+1, in+i+1, len-i-1);
	return root;
}
void main(void)
{
	int i;
	int array[] = {4,2,1,3,5,6};
	int in[] = {1,2,3,4,5,6,7};
	int pre[] ={4,2,1,3,6,5,7};
	bi_tree_t *node = NULL, *root = NULL;
	
	root = rebuild_pre_in_order(pre, in, sizeof(in)/sizeof(in[0]));
	/*for (i = 0; i < sizeof(array)/sizeof(int); i++) {
		node = (bi_tree_t *)malloc(sizeof(bi_tree_t));
		if (node) {
			memset(node, 0, sizeof(bi_tree_t));
			node->val = array[i];
			//if ((root = insert_bst_1(root, node)))
			if (insert_bst(&root, node) == 0)
				printf("insert %d to root successfully\n", array[i]);
			else 
				printf("insert %d to root Failed\n", array[i]);
		} else {
			printf("Failed to alloc memory for %d, insertion failed\n", array[i]);
		}
	}*/
	//root->val = 10;
	printf("in-order tree traverse\n");
	inorder_visit(root);
	printf("\n");
	printf("pre-order tree traverse\n");
	preorder_visit(root);
	printf("\n");
	printf("post-order tree traverse\n");
	postorder_visit(root);
	printf("\n");
	if (is_binary_search_tree1(root))
		printf("min-max: the tree is binary search tree\n");
	if (is_binary_search_tree2(root))
		printf("in-order: the tree is binary search tree\n");
	node = find_smallest_node(root);
	if (node) {
		printf("smallest number is %d\n", node->val);
	}
	bi_tree_t *n;
	for (i = 0; i < sizeof(array)/sizeof(int); i++) {
		node = find_node(root, array[i]);
		if (node) {
			if ((n = in_order_succeesor(root, node)))
				printf("%d succsesor %d\n", array[i], n->val);
			else 
				printf("%d have no succsesor\n", array[i]);
			found = 0;
			if ((n = inorder_suc(root, node)))
				printf("%d succsesor %d\n", array[i], n->val);
			else 
				printf("%d have no succsesor\n", array[i]);
		} else {
			printf("%d not found\n", array[i]);
		}
	}
	del_bst_node(root, 14);
	inorder_visit(root);
	printf("\n");
	return;
}
